Construire un graphe k-régulier - Corrigé

 Énoncé

1. Le cas  \(k=2\) .
Soit un entier naturel non nul  \(n\) . Peut-on construire un graphe connexe d'ordre \(n\)  dont tous les sommets sont de degré \(k=2\) ?

2. Justifier que, pour tout entier  \(k\)  pair non nul, et tout entier naturel non nul  \(n\) , on peut construire un graphe connexe d'ordre  \(n\)  dont tous les sommets sont de degré  \(k\) .

3. Le cas  \(k=3\) .
    a. Peut-on construire un graphe d'ordre 4 dont tous les sommets sont de degré  \(k=3\)  ?
    b. Peut-on construire un graphe d'ordre 5 dont tous les sommets sont de degré  \(k=3\)  ?
    c. Peut-on construire un graphe d'ordre 6 dont tous les sommets sont de degré  \(k=3\)  ?
    d. Donner une condition nécessaire sur  \(n\)  pour pouvoir construire un graphe d'ordre  \(n\)  dont tous les sommets sont de degré 3.
    e. Cette condition nécessaire est-elle suffisante ?

Solution

1. La réponse est oui, un polygone à  \(n\)  sommets figure un tel graphe.

2. Posons  \(k=2p\) .
On peut reprendre le polygone précédent. Il suffit d'ajouter  \((p-1)\) boucles que nécessaire sur chaque sommet, ou de mettre  \(p\)  arêtes parallèles sur chaque côté du polygone.

3. a. Pour  \(n=4\) , un rectangle avec ses diagonales figure un tel graphe.
    b. Pour  \(n=5\) , la somme des degrés des sommets serait égale à  \(15\) . Or, la somme des degrés est égale au double du nombre d'arêtes (nombre pair), donc c'est impossible.
    c. Pour  \(n=6\) , on peut dessiner un hexagone avec 3 diagonales reliant des sommets distincts.
    d. Il faut que  \(n\)  soit pair, sinon comme dans le cas 3.b. la somme des degrés est impaire.
    e. Oui, cette condition est suffisante. Dans le cas où  \(n=2p\)  est pair, il suffit de tracer le polygone puis de tracer toutes les grandes diagonales (c'est-à-dire qu'on relie chaque sommet  \(A_i\)  pour  \(i\)  compris entre  \(1\) et  \(p\)  au sommet  \(A_{i+p}\) ).